Section: Application Domains

Planning, Scheduling, and Logistic Problems

Inventory routing problems combine the optimization of product deliveries (or pickups) with inventory control at customer sites. We considered an industrial application where one must construct the planning of single product pickups over time; each site accumulates stock at a deterministic rate; the stock is emptied on each visit. We have developed a truncated branch-and-price algorithm: periodic plans are generated for vehicles by solving a multiple choice knapsack subproblem; the global planning of customer visits is generated by solving a master program. Confronted with the issue of symmetry in time, we used a state-space relaxation idea. Our algorithm provides solutions with reasonable deviation from optimality for large scale problems (260 customer sites, 60 time periods, 10 vehicles) coming from industry [15] . We previously developed approximate solutions to a related problem combining vehicle routing and planning over a fixed time horizon (solving instances involving up to 6000 pick-ups and deliveries to plan over a twenty day time horizon with specific requirements on the frequency of visits to customers [67] .

We participated to the project on an airborne radar scheduling. For this problem, we developed fast heuristics  [53] and exact algorithms  [39] . A substantial research has been done on machine scheduling problems. A new compact MIP formulation was proposed for a large class of these problems [38] . An exact decomposition algorithm was developed for the NP-hard maximizing the weighted number of late jobs problem on a single machine  [74] . A dominant class of schedules for malleable parallel jobs was discovered in the NP-hard problem to minimize the total weighted completion time  [76] . We proved that a special case of the scheduling problem at cross docking terminals to minimize the storage cost is polynomially solvable  [77] , [75] . Finally, we participated in writing an invited survey in French on solution approaches for machine scheduling problems in general  [40] .

Another application area in which we have successfully developed MIP approaches is in the area of tactical production and supply chain planning. In [37] , we proposed a simple heuristic for challenging multi-echelon problems that makes effective use of a standard MIP solver. [36] contains a detailed investigation of what makes solving the MIP formulations of such problems challenging; it provides a survey of the known methods for strengthening formulations for these applications, and it also pinpoints the specific substructure that seems to cause the bottleneck in solving these models. Finally, the results of [41] provide demonstrably stronger formulations for some problem classes than any previously proposed.

We have been developing robust optimization models and methods to deal with a number of applications like the above in which uncertainty is involved. In [50] , [49] , we analyzed fundamental MIP models that incorporate uncertainty and we have exploited the structure of the stochastic formulation of the problems in order to derive algorithms and strong formulations for these and related problems. These results appear to be the first of their kind for structured stochastic MIP models. In addition, we have engaged in successful research to apply concepts such as these to health care logistics [43] . We considered train timetabling problems and their re-optimization after a perturbation in the network [52] , [51] . The question of formulation is central. Models of the literature are not satisfactory: continuous time formulations have poor quality due to the presence of discrete decision (re-sequencing or re-routing); arc flow in time-space graph blow-up in size (they can only handle a single line timetabling problem). We have developed a discrete time formulation that strikes a compromise between these two previous models. Based on various time and network aggregation strategies, we develop a 2-stage approach, solving the contiguous time model having fixed the precedence based on a solution to the discrete time model.